package uestc.lj.basicPromotion.tree;

/**
 * @Author:Crazlee
 * @Date:2021/11/27
 */
public class Code04_IsBSTByMorrisTravel {
	public static class Node {
		public int value;
		Node left;
		Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static boolean isBST(Node root) {
		if (root == null) {
			return true;
		}
		Node cur = root;
		Node mostRight = null;
		int preValue = Integer.MIN_VALUE;
		while (cur != null) {
			mostRight = cur.left;
			if (mostRight != null) {
				while (mostRight.right != null && mostRight.right != cur) {
					mostRight = mostRight.right;
				}
				if (mostRight.right == null) {
					mostRight.right = cur;
					cur = cur.left;
					continue;
				} else {
					mostRight.right = null;
				}
			}
			if (cur.value <= preValue) {
				return false;
			}
			preValue = cur.value;
			cur = cur.right;
		}
		return true;
	}
}
